# -*- coding: utf-8 -*-
"""
Created on Fri Dec 13 14:48:10 2013

@author: Liang Zhang
"""

from Queue import PriorityQueue

'''
return haffman code[tuple]
nodes:all nodes
cur:the nodes that haven't add to tree
'''
class __node:
    parent=None
    def __init__(self,value):
        self.value=value
    def __cmp__(self,other):
        if other==None:
            return 1
        if(self.value<other.value):
            return -1
        elif self.value==other.value:
            return 0
        else:
            return 1

def huffman(data):
    nodes=[]
    cur=PriorityQueue()
    for x in data:
        nodes.append(__node(x))
    for x in nodes:
        cur.put(x)
    #build tree
    while cur.qsize()>1:
        min1=cur.get()
        min2=cur.get()
        min1.bit=0
        min2.bit=1
        new_node=__node(min1.value+min2.value)
        nodes.append(new_node)
        min1.parent=min2.parent=new_node
        cur.put(new_node)
    #get huffman code
    code=[]
    for i in range(len(data)):
        ptr=nodes[i]
        c=[]
        while ptr.parent!=None:
            c.append(ptr.bit)
            ptr=ptr.parent
        code.append(tuple(reversed(c)))
    return code
                        
if __name__=="__main__":
    print huffman([1,2,3,4,8,17])